자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는, 1보다 큰 자연수이다. 가장 간단한 방법으로 2 ~ N-1까지 나눠버려 하나라도 나눠떨어지는가를 확인하는 방법이 있다. 이는 한개의 숫자에 대해 소수여부를 판단하는대 O(N)의 시간복잡도를 갖게 된다. N개의 수의 소수 판단은 O(N^2)의 시간복잡도를 갖게 되므로 이는 실제 알고리즘 문제풀이에서 사용하기 버거운 시간이기에 사용하지 않는다. 이를 해결하기 위한 2가지 소수 판별법 알고리즘이 있다.